package 蓝桥._2024.砍柴;

import java.util.*;

public class Main4 {
    static int max = 100010;
    // 素数表: 也是合法操作表
    static List<Integer> primeList = new ArrayList<>();
    // dp[i]: 1->长度为i时先手必赢
    static int[] dp = new int[max];

    static void init(){

        boolean[] isPrime = new boolean[max];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        // 素数筛：如果i是素数，那么i的倍数都不是素数
        for(int i = 2;i < max;i++ ){
            if(isPrime[i]){
                for(int j= 2 * i;j<max;j+=i){
                    isPrime[j] = false;
                }
            }
        }
        for (int i = 0; i < max; i++) {
            if(isPrime[i])
                primeList.add(i);
        }

        dp[2] = 1;
        for(int i= 2; i<max;i++){
            for(int j=0;j<primeList.size();j++){
                int len = i - primeList.get(j);
                if(len<0)
                    break;
                if(dp[len]==0) { // 为0则说明下一个人必输, 可以在这结束。
                    dp[i] = 1;
                    break;
                }
                // 若为1，则说明当前的操作不能赢，可继续尝试其他方案（每个人都按最优来）
            }
        }

    }

    public static void main(String[] args) {

        init();

        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        int[] lens = new int[T];
        for (int i = 0; i < T; i++) {
            lens[i] = scan.nextInt();
        }

        for(int i=0;i < T;i++){
            System.out.println(dp[lens[i]]);
        }

        scan.close();

    }
}
